package collection

type Heap[T any] struct {
	_data []T
	count int
	less  func(a, b T) bool
}

func createHeap[T any](cap int, less func(a, b T) bool) *Heap[T] {
	var h = &Heap[T]{}
	h._data = make([]T, cap)
	h.count = 0
	h.less = less
	return h
}

func (h *Heap[T]) _verify(root int) {
	var max = 0
	var left = root*2 + 1
	var right = left + 1
	if left < h.count {
		if h.less(h._data[root], h._data[left]) {
			max = 1
		}
	} else {
		return
	}
	if right < h.count {
		if max == 0 {
			if h.less(h._data[root], h._data[right]) {
				max = 2
			}
		} else {
			if h.less(h._data[left], h._data[right]) {
				max = 2
			}
		}
	}
	if max == 0 {
		return
	} else if max == 1 {
		t := h._data[root]
		h._data[root] = h._data[left]
		h._data[left] = t
		h._verify(left)
	} else {
		t := h._data[root]
		h._data[root] = h._data[right]
		h._data[right] = t
		h._verify(right)
	}

}
func (h *Heap[T]) Add(vs ...T) {
	for _, v := range vs {
		if h.count < len(h._data) {
			h._data[h.count] = v

		} else {
			h._data = append(h._data, v)
		}
		h.count++
		for i := (h.count - 2) / 2; i > 0; i = (i - 1) / 2 {
			h._verify(i)
		}
		h._verify(0)
	}
}

func (h *Heap[T]) Pop() T {
	if h.count == 0 {
		panic("empty")
	}
	v := h._data[0]
	h._data[0] = h._data[h.count-1]
	h.count--
	h._verify(0)
	return v
}
